package order;

import java.util.ArrayList;

/**
 * 排序
 */
public class Sort {

    //排序1、直接插入排序
    public static ArrayList<Integer> ZSort(ArrayList<Integer> list1){
        int i ,j,temp;
        if (list1.size()<1){
            return list1;
        }
        for (i=1;i<list1.size();i++){
            if (list1.get(i)<list1.get(i-1)){
                temp=list1.get(i);
                for (j=i-1;j>=0 && list1.get(j)>temp;j--){
                    list1.set(j+1,list1.get(j));
                }
                list1.set(j+1,temp);
            }
        }
        return list1;

    }

    //冒泡排序
    public static ArrayList<Integer> MSort(ArrayList<Integer> list1){
        if (list1.size()<1){
            return list1;
        }
        for (int i=0;i<list1.size()-1;i++){
            boolean type=false;
            for (int j=list1.size()-1;j>i;j--){
                if (list1.get(j)<list1.get(j-1)){
                    int temp=list1.get(j);
                    list1.set(j,list1.get(j-1));
                    list1.set(j-1,temp);
                    type=true;
                }
            }
            if (type==false){
                return list1;
            }

        }
        return list1;

    }

    //快速排序
    public static ArrayList<Integer> KSort(ArrayList<Integer> list1,int low,int high){
        if (list1.size()<1){
            return list1;
        }
        if (low<high){
            int pre=parent(list1,low,high);
            KSort(list1,low,pre-1);
            KSort(list1,pre+1,high);

        }
        return list1;

    }

    private static int parent(ArrayList<Integer> list1, int low, int high) {
        int pre=list1.get(low);
        while (low<high){
            while (low<high){
                while (low<high && list1.get(high)>pre){
                    high--;
                }
                list1.set(low,list1.get(high));

                while (low<high &&list1.get(low)<pre){
                    low++;
                }
                list1.set(high,list1.get(low));
            }
        }
        list1.set(low,pre);
        return low;


    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(83);
        list.add(40);
        list.add(63);
        list.add(84);
        list.add(35);
        list.add(96);
        list.add(57);
        list.add(39);
        list.add(79);
        //ArrayList<Integer> list1 = ZSort(list);
        //ArrayList<Integer> list1 = MSort(list);
        ArrayList<Integer> list1 = KSort(list,0,list.size()-1);
        for (int a :list1) {
            System.out.println(a);
        }

    }

}
